package algorithm.easy;

import java.util.IntSummaryStatistics;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.easy
 * @Author: 江岸
 * @CreateTime: 2021-03-13 17:07
 * @Description:
 */
class MyHashSet705{
    boolean[] arr;

    //超大数组解法
    /** Initialize your data structure here. */
    public MyHashSet705() {
        arr = new boolean[1000001];
    }

    public void add(int key) {
        arr[key] = true;
    }

    public void remove(int key) {
        arr[key] = false;
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return arr[key];
    }
}

//官方解法 分桶数组

/**
 * 事实上我们还可以实现一个类似「bitmap」数据结构。
 *
 * 使用 int 中的每一位代表一个位置。
 *
 * 由于数据范围为 0 <= key <= 10^6，我们最多需要的 int 数量不会超过 40000。
 *
 * 因此我们可以建立一个 buckets 数组，数组装载的 int 类型数值。
 *
 *     先对 key 进行 key / 32，确定当前 key 所在桶的位置（大概位置）
 *     再对 key 进行 key % 32，确定当前 key 所在桶中的哪一位（精确位置）
 *
 * 根据位运算对「精确位置」进行修改。
 *
 * 作者：AC_OIer
 * 链接：https://leetcode-cn.com/problems/design-hashset/solution/yi-ti-san-jie-jian-dan-shu-zu-lian-biao-nj3dg/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class MyHashSet2 {
    int[] bs = new int[40000];
    public void add(int key) {
        //分割小的桶
        int bucketIdx = key / 32;
        //
        int bitIdx = key % 32;
        setVal(bucketIdx, bitIdx, true);
    }

    public void remove(int key) {
        int bucketIdx = key / 32;
        int bitIdx = key % 32;
        setVal(bucketIdx, bitIdx, false);
    }

    public boolean contains(int key) {
        int bucketIdx = key / 32;
        int bitIdx = key % 32;
        return getVal(bucketIdx, bitIdx);
    }

    void setVal(int bucket, int loc, boolean val) {
        if (val) {
            int u = (bs[bucket] | (1 << loc));
            bs[bucket] = u;
        } else {
            int u = bs[bucket] & ~(1 << loc);
            bs[bucket] = u;
        }
    }

    boolean getVal(int bucket, int loc) {
        int u = (bs[bucket] >> loc) & 1;
        return u == 1;
    }
}


